home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Libraries / Scripting / Source / StevesRgExp.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1995-09-09  |  13.2 KB  |  415 lines  |  [TEXT/MPCC]
  1. /*---------------------------------------------------------------
  2.     Copyright 1995, Steve Israelson
  3.     
  4.     I own this code.  You are free to use this code in any software
  5.     you want.  You may not sell this source code at all, you can 
  6.     sell your product though.  If you want to include this code
  7.     in any code collection (CD-Roms etc) this is OK as long as
  8.     I get a complimentary copy.
  9.             Steve.
  10.     
  11.     Regular expression matching.  The RegExp::Parse() function will
  12.     create a new regular expression object based on your input string.
  13.     You can then ask this object if it matches a string and it will
  14.     return true or false.  Groups of these objects can perform miracles.
  15.     
  16.     These are the regular expression meta characters.  I have no text
  17.     defining what the standard characters are, so I made these up from
  18.     memory.  You can add more if you want, its easy.
  19.     
  20.     ^    Begining of line.
  21.     $    End of line.
  22.     []    Set.
  23.         a-z    A range of characters in a set.
  24.         ~    The following characters are not in the set.
  25.     *    0 or more of the previous pattern.
  26.     +    1 or more of the previous pattern.
  27.     .    Any character.
  28.     |    Or.  Used between any two patterns. NOT IMPLEMENTED!!!!!
  29.     &    Parameter.  The previous pattern is a parameter.
  30.     /    The next character is a literal.
  31.     All other characters are literals.
  32.     
  33.     Note:  This parser is based on the ideas presented in the DrDobbs
  34.     Sourcebook magazine July/August 1995 issue.  The article is by
  35.     Todd D. Esposito and Andrew K. Johnson.  Before reading this
  36.     article and entering and debugging their code, I had very little
  37.     experience doing a scripting system.  The concepts behind
  38.     their system are more powerful than the ones I came up with.
  39.     The concept behind this code is almost the same as the concepts
  40.     they presented, but this implementation is more complete, and
  41.     thus more usable for end users.
  42. ---------------------------------------------------------------*/
  43.  
  44. #include "StevesRgExp.h"
  45. #include <String.h>
  46.  
  47. /*---------------------------------------------------------------
  48.     Creates a linked list of regular expressions representing
  49.     the text.  The root of the list will be returned.
  50.     Pass in the text containing the expression.
  51.     owner is used internally, so pass in nil.  
  52.     Also pass in the ID for this expression so you
  53.     can figure out what expression matched the text.
  54. ---------------------------------------------------------------*/
  55. RegExp *RegExp::Parse(char *text, RegExp *owner, long exprID)
  56.     {
  57.     // parse the text and determine what type of expression
  58.     // is in it.  Make that type of reg exp object and
  59.     // continue until the text is exhausted
  60.     RegExp        *theExpression = nil;
  61.  
  62.     switch (*text++)
  63.         {
  64.         case '^':    // beginning of line
  65.             theExpression = new RBeginLine(text, exprID);
  66.             break;
  67.         case '$':    // end of line
  68.             theExpression = new REndLine(text, exprID);
  69.             break;
  70.         case '[':    // set
  71.             theExpression = new RSetExpr(text, exprID);
  72.             break;
  73.         case '*':    // zero or more
  74.             if (owner)
  75.                 owner->type = kReg_ZeroOrMore;
  76.             return Parse(text, owner, exprID);
  77.             break;
  78.         case '+':    // one or more
  79.             if (owner)
  80.                 owner->type = kReg_OneOrMore;
  81.             return Parse(text, owner, exprID);
  82.             break;
  83.         case '.':    // any char
  84.             theExpression = new RAnyChar(text, exprID);
  85.             break;
  86.         case '|':    // or
  87.             theExpression = new ROrExpr(text, exprID);
  88.             break;
  89.         case '&':    // previous was a parameter
  90.             if (owner)
  91.                 owner->parameter = true;
  92.             return Parse(text, owner, exprID);
  93.             break;
  94.         case '/':    // literalize next char, handled in RLiteral
  95.         default:    // literal
  96.             theExpression = new RLiteral(text - 1, exprID);
  97.             break;
  98.         case 0:        // end of text, do nothing
  99.             break;
  100.         }
  101.     return theExpression;
  102.     }
  103.  
  104. /*---------------------------------------------------------------
  105.     Construct a regular expression based on some text.
  106.     You MUST call     next = Parse(text, this, newID);
  107.     where text points to the characters that are left after
  108.     you made your expression.
  109. ---------------------------------------------------------------*/
  110. RegExp::RegExp(long newID)
  111.     {
  112.     ID = newID;
  113.     next = nil;
  114.     type = kReg_Once;    // default type
  115.     parameter = false;
  116.     }
  117.  
  118. /*---------------------------------------------------------------
  119.     Toast this object, but toast the next one first.
  120. ---------------------------------------------------------------*/
  121. RegExp::~RegExp()
  122.     {
  123.     if (next)
  124.         delete next;
  125.     }
  126.  
  127. /*---------------------------------------------------------------
  128.     Match the regular expression with some text.
  129.     Pass in the text to match, the position of starting character
  130.     to begin matching on, or 0 for the first character.  Pass
  131.     in a pointer to a short if you want to know the position
  132.     of the next un-matched character, or nil if you don't.
  133.     Pass in a list to hold the parameters, or nil if you
  134.     don't want any parameters back.
  135.     If we match, then the next expression in our list is tried.
  136.     If the next one fails, then we try to match again, until
  137.     we fail or the match succeeds.  MatchOne() internally uses
  138.     the nextChar variable to keep track of how many characters
  139.     its matched, and MUST set it to the next character that
  140.     was un-matched.  The very first time you are called it will
  141.     be -1.
  142. ---------------------------------------------------------------*/
  143. Boolean RegExp::Match(char *text, short start, short *last, LList *paramList)
  144.     {
  145.     short        nextChar = -1;
  146.  
  147.     while (1)
  148.         {
  149.         // can we match our own criteria?
  150.         if (!MatchOne(text, start, &nextChar))
  151.             return false;
  152.         // save the position of the last match
  153.         if (!next && last)
  154.             *last = nextChar;
  155.         // can our sub expressions match?
  156.         if (!next || next->Match(text, nextChar, last, paramList))
  157.             {
  158.             // if we have a parameter, then put it in the params here
  159.             if (parameter && paramList)
  160.                 {
  161.                 char    *param = new char[64];    // paramters default to this size, but you could dynamically do it
  162.                 strncpy(param, text + start, nextChar - start);
  163.                 param[nextChar - start] = 0;        // terminate the string, does strncpy?
  164.                 paramList->InsertItemsAt(1, arrayIndex_First, ¶m);    // add it to the front of the list
  165.                 }
  166.             return true;
  167.             }
  168.         }
  169.     return false;
  170.     }
  171.  
  172. /*---------------------------------------------------------------
  173.     Match the regular expression with some text.
  174.     Over-ride and return true if you match.
  175.     The value of end will be preserved between calls, and 
  176.     will always start with -1.  Start is the index of the first
  177.     character to be considered.
  178. ---------------------------------------------------------------*/
  179. Boolean RegExp::MatchOne(char *text, short start, short *end)
  180.     {
  181.     *end = start;
  182.     return false;
  183.     }
  184.  
  185. /*---------------------------------------------------------------
  186.     Construct a regular expression based on some text.
  187. ---------------------------------------------------------------*/
  188. RBeginLine::RBeginLine(char *text, long newID) : RegExp(newID)
  189.     {
  190.     // nothing to do, make the next one in our list.
  191.     next = Parse(text, this, newID);
  192.     }
  193.  
  194. /*---------------------------------------------------------------
  195.     Match the regular expression with some text.
  196. ---------------------------------------------------------------*/
  197. Boolean RBeginLine::MatchOne(char *text, short start, short *end)
  198.     {
  199.     if (*end == -1 && !start)    // we only match if we are at the start of the line, ie start = 0
  200.         {
  201.         *end = start;
  202.         return true;
  203.         }
  204.     return false;
  205.     }
  206.  
  207. /*---------------------------------------------------------------
  208.     Construct a regular expression based on some text.
  209. ---------------------------------------------------------------*/
  210. REndLine::REndLine(char *text, long newID) : RegExp(newID)
  211.     {
  212.     // nothing to do, make the next one in our list.
  213.     next = Parse(text, this, newID);
  214.     }
  215.  
  216. /*---------------------------------------------------------------
  217.     Match the regular expression with some text.
  218. ---------------------------------------------------------------*/
  219. Boolean REndLine::MatchOne(char *text, short start, short *end)
  220.     {
  221.     // we only match if there are no more characters left in this line
  222.     if (*end == -1 && (text[start] == 0 || text[start] == '\r'))
  223.         {
  224.         *end = start;
  225.         return true;
  226.         }
  227.     return false;
  228.     }
  229.  
  230. /*---------------------------------------------------------------
  231.     Construct a regular expression based on some text.
  232.     This makes an expression that can match a set.  Simply
  233.     uses an array of booleans to keep track of which
  234.     characters are in the set.  Could be better, but...
  235.     The text should be "[...]" where ... can be any individual
  236.     characters.  you can also specify a range with the '-' character.
  237.     Use '~' when you want to remove some chars from the set.
  238.     [a-zA-Z~dD]  matches all alphabetical chars except d and D
  239. ---------------------------------------------------------------*/
  240. RSetExpr::RSetExpr(char *text, long newID) : RegExp(newID)
  241.     {
  242.     // remove the set from the text
  243.     for (int x = 0; x < 256; ++x)
  244.         charSet[x] = 0;
  245.     char    state = 1;
  246.     char    prevChar = 0;
  247.     while (*text && *text != ']')
  248.         {
  249.         if (*text == '/')    // quote the next character, ie the ']', or the '/'
  250.             ++text;
  251.         if (*text == '-' && prevChar && *(text + 1))    // set a whole range
  252.             {
  253.             ++text;
  254.             for (int x = prevChar; x <= *text; ++x)
  255.                 charSet[x] = state;
  256.             }
  257.         else if (*text == '~')
  258.             state = 0;
  259.         else
  260.             charSet[*text] = state;
  261.         prevChar = *text;
  262.         ++text;    // next character
  263.         }
  264.     if (*text)    // skip the ']'
  265.         ++text;
  266.  
  267.     // make the next one in our list.
  268.     next = Parse(text, this, newID);
  269.     }
  270.  
  271. /*---------------------------------------------------------------
  272.     Match the regular expression with some text.
  273. ---------------------------------------------------------------*/
  274. Boolean RSetExpr::MatchOne(char *text, short start, short *end)
  275.     {
  276.     if (type == kReg_Once && *end != -1)    // end is -1 the first time, so if it is not 0 then...
  277.         return false;
  278.     if (type == kReg_ZeroOrMore && *end == -1)// we first try matching 0
  279.         {
  280.         *end = start;
  281.         return true;
  282.         }
  283.     if (*end == -1)        // the first time through, try only the first char
  284.         *end = start;
  285.     for (int x = start; x <= *end; ++x)
  286.         if (!charSet[text[x]])
  287.             return false;
  288.     *end = *end + 1;    // we matched this char, so move end.
  289.     return true;
  290.     }
  291.  
  292. /*---------------------------------------------------------------
  293.     Construct a regular expression based on some text.
  294. ---------------------------------------------------------------*/
  295. RAnyChar::RAnyChar(char *text, long newID) : RegExp(newID)
  296.     {
  297.     // make the next one in our list.
  298.     next = Parse(text, this, newID);
  299.     }
  300.  
  301. /*---------------------------------------------------------------
  302.     Match the regular expression with some text.
  303. ---------------------------------------------------------------*/
  304. Boolean RAnyChar::MatchOne(char *text, short start, short *end)
  305.     {
  306.     if (type == kReg_Once && *end != -1)    // end is -1 the first time, so if it is not 0 then...
  307.         return false;
  308.     if (type == kReg_ZeroOrMore && *end == -1)// we first try matching 0
  309.         {
  310.         *end = start;
  311.         return true;
  312.         }
  313.     if (*end == -1)        // the first time through, try only the first char
  314.         *end = start;
  315.     // since we match anything, we do not need to make any checks here
  316.     // EXCEPT to see if we are at the end of the string
  317.     if (!text[*end])
  318.         return false;    // no more chars to match
  319.     *end = *end + 1;    // we matched this char, so move end.
  320.     return true;
  321.     }
  322.  
  323. /*---------------------------------------------------------------
  324.     Construct a regular expression based on some text.
  325. ---------------------------------------------------------------*/
  326. ROrExpr::ROrExpr(char *text, long newID) : RegExp(newID)
  327.     {
  328.     // NOT IMPLEMENTED yet
  329.     // make the next one in our list.
  330.     next = Parse(text, this, newID);
  331.     }
  332.  
  333. /*---------------------------------------------------------------
  334.     Match the regular expression with some text.
  335. ---------------------------------------------------------------*/
  336. Boolean ROrExpr::MatchOne(char *text, short start, short *end)
  337.     {
  338.     return false;    // We do not implement OR yet (how would we?)
  339.     }
  340.  
  341. /*---------------------------------------------------------------
  342.     Construct a regular expression based on some text.
  343.     Collect characters until a meta character is encountered.
  344.     This is our literal.
  345. ---------------------------------------------------------------*/
  346. RLiteral::RLiteral(char *text, long newID) : RegExp(newID)
  347.     {
  348.     Boolean        done = false;
  349.     short        index = 0;
  350.     
  351.     while (!done)
  352.         {
  353.         switch (*text)
  354.             {
  355.             case 0:    
  356.             case '^':    // beginning of line
  357.             case '$':    // end of line
  358.             case '[':    // set
  359.             case '*':    // zero or more
  360.             case '+':    // one or more
  361.             case '.':    // any char
  362.             case '|':    // or
  363.                 done = true;
  364.                 break;
  365.             case '/':    // literalize next char
  366.                 ++text;    // skip the slash and drop into the literal code
  367.             default:    // literal
  368.                 buffer[index++] = *text++;
  369.                 break;
  370.             }
  371.         }
  372.     buffer[index] = 0;    // terminate string
  373.     next = Parse(text, this, newID);
  374.     }
  375.  
  376. /*---------------------------------------------------------------
  377.     Match the regular expression with some text.
  378.     Match the literal possible 0 or more times.
  379. ---------------------------------------------------------------*/
  380. Boolean RLiteral::MatchOne(char *text, short start, short *end)
  381.     {
  382.     short        x;
  383.     if (type == kReg_Once && *end != -1)    // end is -1 the first time, so if it is not 0 then...
  384.         return false;
  385.     if (type == kReg_ZeroOrMore && *end == -1)    // we first try matching 0
  386.         {
  387.         *end = start;
  388.         return true;
  389.         }
  390.     if (*end == -1)        // the first time through, try only the first set
  391.         *end = start;
  392.     for (x = start; x <= *end;)
  393.         {
  394.         short    i = 0;
  395.         while (buffer[i])    // match the entire buffer, return false if we hit the end of the string
  396.             if (!text[x] || (buffer[i++] != text[x++]))
  397.                 return false;
  398.         }
  399.     *end = x;    // the end has moved 
  400.     return true;
  401.     }
  402.  
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.  
  410.  
  411.  
  412.  
  413.  
  414.  
  415.